# 59/100 回溯-单词搜索
# leetcode第79题: https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/26
from collections import Counter

from leetcode.test import test_function as tf


def exist_bt(board: list[list[str]], word: str) -> bool:
    """我的方法, 但是超时了
    主要原因是每次都需要完全拼凑出整个单词才返回结果, 这样就造成每次都要递归到最深层才能返回
    """
    res = False
    length = len(word)
    m, n, = len(board), len(board[0])

    def neighbors(r, c) -> (int, int):
        nonlocal m, n
        for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
            if 0 <= nr < m and 0 <= nc < n:
                yield nr, nc

    def back_tracking(path, cursor, used):
        """
        :param used: 标记矩阵中的元素是否已经访问过
        :param path: 表示已经选择的路径
        :param cursor: (r, c)目前位置的行号
        """
        nonlocal res, length
        if path == word:
            res = True
            return
        if len(path) >= length:
            return
        for nr, nc in neighbors(cursor[0], cursor[1]):
            if used[nr][nc]:
                continue
            path += board[nr][nc]
            used[nr][nc] = True
            back_tracking(path, (nr, nc), used)
            path = path[:-1]
            used[nr][nc] = False

    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0]:
                used = [[False] * n for _ in range(m)]
                used[i][j] = True
                back_tracking(board[i][j], (i, j), used)
                if res:
                    return True
    return False


def exist_bt_opt(board: list[list[str]], word: str) -> bool:
    """优化了我此前的代码, 主要是减少了递归的深度
    """

    def neighbors(r, c) -> (int, int):
        nonlocal m, n
        for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
            if 0 <= nr < m and 0 <= nc < n:
                yield nr, nc

    def back_tracking(r, c, k, used):
        if board[r][c] != word[k]:  # 主要修改在这里
            return False
        if k == len(word) - 1:
            return True

        res = False
        used[r][c] = True
        for nr, nc in neighbors(r, c):
            if used[nr][nc]:
                continue
            if back_tracking(nr, nc, k + 1, used):
                res = True
                break

        used[r][c] = False
        return res

    m, n, = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0]:
                used = [[i == row and j == col for col in range(n)] for row in range(n)]
                if back_tracking(i, j, 0, used):
                    return True
    return False


def exist_ultra(board: list[list[str]], word: str) -> bool:
    """增加了一段统计word字数的代码, 可以大幅减少计算量.
    此外, 根据word的首字符和尾字符出现的数量来决定是否反转字符串,
    优先计算出现数量较少的字符可以减少递归的深度, 且反转字符串不影响最终的结果.
    """

    cnt = Counter(c for row in board for c in row)  # 统计每个字符出现的次数
    if not cnt >= Counter(word):  # 不满足字符出现数
        return False

    if cnt[word[-1]] < cnt[word[0]]:  # 反转
        word = word[::-1]

    def neighbors(r, c) -> (int, int):
        nonlocal m, n
        for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
            if 0 <= nr < m and 0 <= nc < n:
                yield nr, nc

    def back_tracking(r, c, k, used):
        if board[r][c] != word[k]:
            return False
        if k == len(word) - 1:
            return True

        res = False
        used[r][c] = True
        for nr, nc in neighbors(r, c):
            if used[nr][nc]:
                continue
            if back_tracking(nr, nc, k + 1, used):
                res = True
                break

        used[r][c] = False
        return res

    m, n, = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0]:
                used = [[i == row and j == col for col in range(n)] for row in range(n)]
                if back_tracking(i, j, 0, used):
                    return True
    return False


if __name__ == '__main__':
    inp = [{"board": [["A", "B", "C", "E"],
                      ["S", "F", "C", "S"],
                      ["A", "D", "E", "E"]],
            "word": "ABCCED"},

           {"board": [["A", "B", "C", "E"],
                      ["S", "F", "C", "S"],
                      ["A", "D", "E", "E"]],
            "word": "SEE"},

           {"board": [["A", "B", "C", "E"],
                      ["S", "F", "C", "S"],
                      ["A", "D", "E", "E"]],
            "word": "BCE"},

           {"board": [["A", "B", "C", "E"],
                      ["S", "F", "C", "S"],
                      ["A", "D", "E", "E"]],
            "word": "ABCB"},

           {"board": [["a", "a", "a", "a"],
                      ["a", "a", "a", "a"],
                      ["a", "a", "a", "a"]],
            "word": "aaaaaaaaaaaaa"},

           {"board": [["A", "A", "A", "A", "A", "A"],
                      ["A", "A", "A", "A", "A", "A"],
                      ["A", "A", "A", "A", "A", "A"],
                      ["A", "A", "A", "A", "A", "A"],
                      ["A", "A", "A", "A", "A", "B"],
                      ["A", "A", "A", "A", "B", "A"]],
            "word": "AAAAAAAAAAAAABB"},
           ]
    out = [True, True, True, False, False, False]

    tf(exist_bt, inp, out)
    tf(exist_bt_opt, inp, out)
    tf(exist_ultra, inp, out)
